// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem648.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=648 lang=cpp
 * @lcpr version=30204
 *
 * [648] 单词替换
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start

class Dict
{

    struct node
    {
        char c;
        bool word_end;
        array<node *, 26> arr;

        node() : c(' '), word_end(false)
        {
            this->arr.fill(nullptr);
        }
    };

    node *root;

private:
    void deleteNode(node *root)
    {
        if (root != nullptr)
        {
            for (auto &n : root->arr)
            {
                deleteNode(n);
                n = nullptr;
            }
            delete root;
        }
    }

public:
    Dict() : root(new node)
    {
    }
    ~Dict()
    {
        deleteNode(root);
        root = nullptr;
    }
    void add(const string &word)
    {
        node *curr = this->root;
        for (int i = 0; i < word.size(); ++i)
        {
            int idx = word[i] - 'a';
            if (curr->arr[idx] == nullptr)
            {
                curr->arr[idx] = new node;
            }
            curr = curr->arr[idx];
            curr->c = word[i];
        }
        curr->word_end = true;
    }
    string search(const string &word)
    {
        string s;
        node *curr = this->root;
        for (auto c : word)
        {
            if (curr != nullptr && curr->arr[c - 'a'] != nullptr)
            {
                s.push_back(c);
                if (curr->arr[c - 'a']->word_end)
                {
                    return s;
                }
                curr = curr->arr[c - 'a'];
            }
            else
            {
                return word;
            }
        }
        return word;
    }
};

class Solution
{
public:
    string replaceWords(vector<string> &dictionary, string sentence)
    {
        Dict d;
        for (auto &s : dictionary)
        {
            d.add(s);
        }
        auto words = splitBySpace(sentence);
        string res;
        for (size_t i = 0; i < words.size(); ++i)
        {
            string replacement = d.search(words[i]);
            // 若未找到前缀，使用原单词
            res += (replacement.empty() ? words[i] : replacement);
            res += " ";
        }
        res.pop_back();
        return res;
    }
    vector<string> splitBySpace(const string &sentence)
    {
        vector<string> res;
        for (int i = 0, j = 0; i < sentence.size(); i = j + 1)
        {
            string tmp;
            for (j = i; j < sentence.size() && sentence[j] != ' '; ++j)
            {
                tmp.push_back(sentence[j]);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

// @lc code=end

/*
// @lcpr case=start
// ["cat","bat","rat"]\n"the cattle was rattled by the battery"\n
// @lcpr case=end

// @lcpr case=start
// ["a","b","c"]\n"aadsfasf absbs bbab cadsfafs"\n
// @lcpr case=end

 */
